package minFallingPathSum;

import java.util.Arrays;

public class Solution {
    public int minFallingPathSum(int[][] grid) {
        // dp[i][j] 表示到grid[i][j] 的最小值
        // dp[i][j-1] = Math.min(dp[i-1]//出去j之外的)
        // dp[i+1][j] = Math.min(dp[i]// 出去j之外的)
        int[][] dp = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid[0].length; i++) {
            dp[0][i] = grid[0][i];
        }
        System.out.println(Arrays.toString(dp[0]));
        for (int i = 0; i < grid.length-1; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < grid[i].length; j++) {
                dp[i+1][j] = getMin(dp[i],j) + grid[i+1][j];
            }
        }
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        int ans = dp[dp.length-1][0];
        for (int i = 1; i < dp[0].length; i++) {
            ans = Math.min(dp[dp.length-1][i],ans);
        }
        return ans;
    }
    // 得到除去arr[j] 之外的最小值
    private int getMin(int []arr,int j){
        Integer min = null;
        for (int i = 0; i < arr.length; i++) {
            if(min == null&& i!=j){
                min = arr[i];
            }else if(min!=null){
                min = Math.min(min,arr[i]);
            }
        }
        if(min == null){
            System.out.println("空的");
            return arr[j];
        }
        return min;
    }
}
